package leetcode.other;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description: https://leetcode.cn/problems/gray-code/description/
 * @Author Ammar
 * @Create 2023/8/3 19:08
 */
public class _89_格雷编码 {
    public static void main(String[] args) {
        new _89_格雷编码().grayCode(2);
    }

    /**
     * n = 0时
     * 0
     * -----------
     * n = 1时
     * 0
     * 1
     * -----------
     * n = 2时，镜子对称，上面+0，下面+1
     * 0 0   0   00 ^ 10 = 10
     * 0 1   1   01 ^ 10 = 11
     * 1 1   3
     * 1 0   2
     * -----------------------
     * n = 3时
     * 0 0 0
     * 0 0 1
     * 0 1 1
     * 0 1 0
     * 1 1 0   010 ^ 100 = 110
     * 1 1 1   011 ^ 100 = 111
     * 1 0 1   001 ^ 100 = 101
     * 1 0 0   000 ^ 100 = 100
     * ^ 异位1  同位0
     * @param n
     * @return
     */
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>();
        res.add(0);
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--) {
                Integer data = res.get(j);
                res.add(head ^ data); // 不考虑二进制的进位时 head + data =  head ^ data
            }
            head <<= 1;
        }
        return res;
    }

    // 公式：n位格雷码序列，就是从0到n位二进制数，
    // 每一个数右移一位 然后 与自身异或。例子 0011 ^ (0001)，
    // 所以 0 1 2 3 的格雷码就是 0 1 3 2
    // n 位格雷码就是 (i >> 1) ^ i
    public List<Integer> grayCode1(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < 1 << n; i++) {
            ret.add((i >> 1) ^ i);
        }
        return ret;
    }

}
